/*
 * arvore.c
 *
 *  Created on: 05/06/2011
 *      Author: joao e sheila
 */

#include "arvore.h"


/* Rotacao a direita */
void rot_dir(no **p) {
    no *aux;
    aux = (*p)->esq;
    (*p)->esq = aux->dir;
    aux->dir = *p;
    *p = aux;
}

/* Rotacao a esquerda */
void rot_esq(no **p) {
    no *aux;
    aux = (*p)->dir;
    (*p)->dir = aux->esq;
    aux->esq = *p;
    *p = aux;
}


/* Insercao na Arvore */
int insereAVL(char *x, no **p, TipoElemento linha, char *nome_livro) {
	int cresceu;
	int auxelem; /*serve pra nao chamar a funcao LocalizaArquivo varias vezes*/

	/* Se a arvore esta vazia insere. */
	if (*p == NULL) {
		*p = (no *) malloc(sizeof(no));
		(*p)->chave = x;
		(*p)->quantidade = 1;
		CriaArquivo(&(*p)->listaarq); /*zera comprimento do arquivo*/
		AdicionaArquivo(nome_livro, &(*p)->listaarq); /* estou usando um ponteiro, por isso um &*/

		Cria(
				&(*p)->listaarq.elementos[(*p)->listaarq.comp_arquivo - 1].linha_do_arquivo); /*comeca no 0 o vetor*/
		Adiciona(
				linha,
				&(*p)->listaarq.elementos[(*p)->listaarq.comp_arquivo - 1].linha_do_arquivo);


		(*p)->dir = (*p)->esq = NULL;
		/* Balanceamento de uma folha e sempre perfeito */
		(*p)->bal = 0;
		/* Esta sub arvore cresceu */
		cresceu = 1;
	}
	/* Senao verifica se tem que inserir a esquerda */
	else if (strcmp((*p)->chave, x) > 0) {
		/* Tenta inserir a esquerda e ve se a sub-arvore cresceu */
		cresceu = insereAVL(x, &(*p)->esq, linha, nome_livro);
		if (cresceu) {

			/* Verifica o estado atual de balanceamento */
			switch ((*p)->bal) {

			/* Se a arvore dir. era maior nao ha crescimento */
			case 1:
				(*p)->bal = 0;
				cresceu = 0;
				break;

				/* Se a arvore dir. tinha tamanho igual, houve crescimento */
			case 0:
				(*p)->bal = -1;
				cresceu = 1;
				break;
				/* Se a sub-arvore da esq. ja era maior, deve-se re-balancear. */
			case -1:
				/* Verifica qual o caso de re-balanceamento. */
				/* Se a arvore da esquerda do filho da esquerda esta mais */
				/* alta basta uma rotacao para direita. */
				if ((*p)->esq->bal == -1) {
					/* Rotacao para direita.*/
					rot_dir(p);
					/* Acerta os balanceamentos. */
					(*p)->bal = (*p)->dir->bal = 0;
				} else {
					/* Rotacao dupla. */

					/* Primeiro a esquerda. */
					rot_esq(&(*p)->esq);
					/* Depois a direita.*/
					rot_dir(p);

					/* Acerta balanceamentos. */
					if ((*p)->bal == -1) {
						(*p)->esq->bal = 0;
						(*p)->dir->bal = 1;
					} else {
						(*p)->dir->bal = 0;
						(*p)->esq->bal = -(*p)->bal;
					}
					(*p)->bal = 0;
				}
				cresceu = 0;
			}

		}
	}
	/* Verifica se tem que inserir a direita. */
	else if (strcmp((*p)->chave, x) < 0) {
		/* Tenta inserir a direita e ve se a sub-arvore cresceu */
		cresceu = insereAVL(x, &(*p)->dir, linha, nome_livro);
		if (cresceu) {
			/* Verifica o estado atual de balanceamento */
			switch ((*p)->bal) {
			/* Se a arvore esq. era maior nao ha crescimento */
			case -1:
				(*p)->bal = 0;
				cresceu = 0;
				break;
				/* Se a arvore esq. tinha tamanho igual, houve crescimento */
			case 0:
				(*p)->bal = 1;
				cresceu = 1;
				break;
				/* Se a arvore da dir. ja era maior, deve-se re-balancear. */
			case 1:
				/* Verifica qual o caso de re-balanceamento. */
				/* Se a arvore da direita do filho da direita esta mais */
				/* alta basta uma rotacao para esquerda. */
				if ((*p)->dir->bal == 1) {
					/* Rotacao para esquerda.*/
					rot_esq(p);
					/* Acerta os balanceamentos. */
					(*p)->bal = (*p)->esq->bal = 0;
				} else {
					/* Rotacao dupla.*/

					/* Primeiro a direita.*/
					rot_dir(&(*p)->dir);
					/* Depois a esquerda. */
					rot_esq(p);

					/* Acerta balanceamentos. */
					if ((*p)->bal == -1) {
						(*p)->esq->bal = 0;
						(*p)->dir->bal = 1;
					} else {
						(*p)->dir->bal = 0;
						(*p)->esq->bal = -(*p)->bal;
					}

					(*p)->bal = 0;
				}
				cresceu = 0;
			}
		}
	} else {

		/* caso se jah tinha palavra na arvore */

		cresceu = 0;
		(*p)->quantidade++;
		if (LocalizaArquivo(nome_livro, &(*p)->listaarq) == FIM) {
			AdicionaArquivo(nome_livro, &(*p)->listaarq);
			Cria(
					&(*p)->listaarq.elementos[(*p)->listaarq.comp_arquivo - 1].linha_do_arquivo); /*comeca no 0 o vetor*/
			Adiciona(
					linha,
					&(*p)->listaarq.elementos[(*p)->listaarq.comp_arquivo - 1].linha_do_arquivo);

			/* resumo desse if: nao tinha o arquivo, entao nao tinha linha, tem que criar*/
		}
		else {
			/*ele ja tem o arquivo, me devolve a posicao*/
			auxelem = LocalizaArquivo(nome_livro, &(*p)->listaarq);
			if (Localiza(linha,
					&(*p)->listaarq.elementos[auxelem].linha_do_arquivo) == FIM)
				Adiciona(linha,
						&(*p)->listaarq.elementos[auxelem].linha_do_arquivo);
		}

	}
	return cresceu;
}

/* Imprime a arvore */
void imprime(no *raiz, int nivel) {
     int i;

     if (raiz == NULL){ return; }

     imprime(raiz->dir, nivel + 1);

     for(i = 0; i < nivel; i++) printf("   ");

     printf("%s(%d) \n", raiz->chave, raiz->quantidade); /*quantas palavras foram encontradas*/
     ImprimeListaArquivo(&raiz->listaarq);
     printf("\n");

     imprime(raiz->esq, nivel + 1);
}

/* Busca x em uma arvore binaria de busca. */
no *busca(char *x, no *raiz) {
   while ((raiz != NULL) && strcmp(raiz->chave, x) != 0) {
         if (strcmp(raiz->chave, x) < 0) raiz = raiz->dir;
            else raiz = raiz->esq;
   }
   return raiz;
}
